#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<cmath>
#include<string>

using namespace std;

string fun1(int n)
{
    vector<int> result(1, 1);
    for (int i = 2; i <= n; i++)
    {
        int next = 0;
        for (int j = 0; j < result.size(); j++)
        {
            int product = result[j] * i + next;
            result[j] = product % 10;
            next = product / 10;
        }

        while (next)
        {
            result.push_back(next % 10);
            next /= 10;
        }
    }

    string res = "";

    for (int i = result.size() - 1; i >= 0; i--)
    {
        res += (result[i] + '0');
    }

    return res;
}

int count(int n, char a)
{
    string res = fun1(n);

    int count = 0;
    for (auto x : res)
    {
        if (x == a)
        {
            count++;
        }
    }

    return count;
}


int main()
{
    int t;
    cin >> t;

    while (t--)
    {
        int n;
        char a;
        cin >> n >> a;
        cout << count(n, a) << endl;
    }
    return 0;
}
